\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{graphicx}
\usepackage{caption}

%\sloppy
\hyphenation{es-ca-lo-na-men-to}

\begin{document}

\include{capa}

\tableofcontents
\newpage

\section{Visão Geral do Sistema Implementado}

A implementação do sistema é mais específica do que foi inicialmente proposto. A proposta inicial era de um sistema de tempo real para o controle de resposta automática à mudança de ambiente de um dispositivo tal qual um robô de exploração ou um sistema de navegação de carros. Na implementação considerou-se apenas um sistema para o controle de um robô.

Para tal, utilizou-se um programa de simulação de robôs móveis para verificar os resultados do desenvolvimento. Esse programa é o \emph{Stage}, o qual é parte do projeto \emph{Player/Stage} da \emph{Sourceforge}. A implementação foi realizada utilizando-se as linguagens C e C++, sendo esta última restrita às funções relacionadas às bibliotecas utilizadas pelo \emph{Stage}, sobre uma plataforma Linux.

O fato do desenvolvimento ter sido feito sobre uma plataforma Linux comum (não RTLinux) tem uma importante implicação. Isso significa que a implementação da política de escalonamento para sistemas de tempo real teria que ser feita utilizando-se dos recursos oferecidos pelo sistema operacional. Isto é, a política de escalonamento escolhida teria que ser implementada sobre a política de escalonamento utilizadas pelo SO. Além disso, utilizou-se de outros recursos para tentar minimizar os efeitos de atraso na execução das tarefas de interesse. Maiores detalhes se encontram na próxima seção.

\section{Descrição dos Módulos}

O programa foi dividido em três módulos principais.

\begin{enumerate}
  \item \textit{dijkstra}: calcula o menor caminho entre dois pontos de um mapa, dada a matriz de ocupação fornecida pelo programa \textit{Stage}, e retorna um vetor com os passos a serem dados para se chegar ao objetivo.
  \item \textit{move\_robot}: responsável por fazer o robô se mover no mapa, dado um caminho do ponto de origem ao ponto desejado fornecido pelo Dijkstra.
  \item \textit{scheduler}: responsável por implementar o EDF, implementar o \textit{timer} periódico, alterar o tipo de escalonamento usado pelo sistema operacional, alterar a prioridade das tarefas de acordo com seus \textit{deadlines}, criar uma área de memória compartilhada para as tarefas trocarem dados, impedir a paginação das páginas relacionadas a esses processos e iniciar a execução das tarefas na ordem correta.
\end{enumerate}


\section{Detalhes de Implementação}

  \subsection{Considerações}

Algumas considerações sobre a implementação do sistema:

\begin{itemize}
  \item O desvio de obstáculos foi implementado somente para o caso de barreiras estáticas, conhecidas antes do cálculo da rota. O motivo é que a inserção de barreiras à medida que o robô se movimenta é dificultada com o uso do \emph{Stage}.
  \item O mapa gerado no \emph{Stage} é convertido para uma matriz de ocupação (obtida através de funções da biblioteca utilizada pelo programa, em C++), que associa a cada coordenada do mapa os valores -1 (se aquela coordenada está livre) ou 1 (caso contrário).
  \item O cálculo de rota é feita utilizando-se um algoritmo de Dijkstra adaptado para a matriz de ocupação citada. Como a matriz de ocupação já informa onde estão os obstáculos, o caminho mínimo gerado pelo algoritmo é construído de forma a evitá-los.
\end{itemize}

  \subsection{Tarefas}

O controle do robô é feito através de duas tarefas principais, cada uma implementada como um programa em separado, e que são executadas através de uma chamada de \emph{posix\_spawn} (semelhante a um \emph{fork}) no processo pai. Esse último é responsável por ordenar as tarefas em ordem crescente de \textit{deadline}, de alterar a política de escalonamento e as prioridades das tarefas, de impedir que haja paginação nas páginas referentes aos processos em questão e de gerar e mandar executar os processos referentes a cada tarefa. As duas tarefas principais, com relação de dependência de uma para a outra, são:

\begin{itemize}
  \item Cálculo da rota: utiliza Dijkstra para calcular o menor caminho, desviando dos obstáculos, do ponto de origem ao ponto de destino no mapa. Retorna um vetor indicando os passos do caminho, que é utilizado como entrada para a próxima tarefa.
  \item Movimentação do robô: feita com auxílio do \emph{Stage} para um determinado mapa e para o caminho retornado no cálculo de rota.
\end{itemize}

Como cada tarefa foi implementada como um programa diferente, foi preciso implementar uma forma de possibilitar a troca de dados entre elas, já que a segunda tarefa precisa do resultado da primeira para executar. A forma utilizada para fazer esse compartilhamento de dados entre as tarefas foi a utilização de uma área de memória compartilhada com uma chave conhecida pelas tarefas. A tarefa de cálculo de rota é responsável por preencher essa área de memória com o vetor contendo o caminho entre o ponto de origem e o de destino. A tarefa de movimentação do robô tem apenas que ler essa área de memória para obter os parâmetros necessários para movimentar o robô. A criação dessa área compartilhada de memória foi feita com o uso dos comandos \emph{shmget} e \emph{shmat}, como mostrado no excerto de código abaixo.

\begin{verbatim}
// Cria area de memoria compartilhada (create & read-write)
if ((*shmid = shmget(key, sizeof(int)*nvertices, IPC_CREAT | 0666)) == -1)
{
    perror("shmget"); 
    exit(-1);
}

// Anexa o processo corrente a area recem criada
if ((shm = shmat(*shmid, NULL, 0)) == (char *) -1) 
{
   perror("shmat");
   exit(-1);
}
\end{verbatim}


  \subsection{Estratégia de Escalonamento}

A política de escalonamento adotada para os processos foi a política do \textit{Earliest Deadline First}, em que os \textit{deadlines} das tarefas são passadas para o programa como parâmetros de execução - como exemplificado na seção seguinte. A política EDF foi escolhida principalmente devido à dependência existente entre as tarefas, já que a tarefa que depende do término da outra terá um \textit{deadline} maior que a anterior. 

Para ordenar as tarefas por ordem de \textit{deadline}, o programa preenche uma estrutura interna para cada tarefa, associando cada uma delas com seu \textit{deadline}. Essa estrutura é mostrada abaixo.
\newline

\begin{verbatim}
struct task_t
{
    char* path;     // Caminho completo do executavel
    short deadline; // Deadline em microssegundos
};
\end{verbatim}

As estruturas preenchidas para cada tarefa são armazenadas em um vetor, o qual é ordenado crescentemente segundo seus \textit{deadlines}.

Como explicado na primeira seção desse documento, para que o EDF tivesse efeito sobre os processos de interesse, foi necessário alterar a política de escalonamento do SO para esses processos para um escalonamento FIFO - essa política de escalonanemnto no Linux é na verdade aplicada em cada uma das filas de prioridades mantidas no SO -, em que prioridades maiores são dadas às tarefas de menores \textit{deadlines}. Pelo fato de se alterar políticas de escalonamento e prioridades de processos dentro do programa, é necessário que sua execução seja feita com privilégios de superusuário.

A alteração da política de escalonamento e das prioridades foi realizada com auxílio dos comandos mostrados a seguir.

\begin{verbatim}
// Redefinicao da politica de escalonamento
struct sched_param param;
param.sched_priority = atoi(argv[1]);
st = sched_setscheduler(0, SCHED_FIFO, &param);

// Redefinicao da prioridade do processo
st = setpriority(PRIO_PROCESS, child, atoi(argv[1]));
\end{verbatim}

  \subsection{Geração das Tarefas}

As tarefas básicas desse sistema são executadas como filhas de um outro processo, como explicado anteriormente. Entretanto, como se trata de uma aplicação de tempo real, optou-se por usar o comando \emph{posix\_spawn} em vez de \emph{fork} seguido de \emph{exec}. Essa opção foi feita por questões de eficiência, uma vez que chamadas de \emph{posix\_spawn} são mais eficientes em termos de tempo do que a outra opção e, consequentemente, são mais apropriadas para aplicações de tempo real. O comando utilizado no código é mostrado a seguir.

\begin{verbatim}
// Cria processo filho inicialmente com mesma politica de 
// escalonamento e prioridade
st = posix_spawn(&child, path, NULL, NULL, arg_list, NULL);
\end{verbatim}

  \subsection{Desabilitação da Paginação}

O comando \emph{mlockall} é utilizado no processo pai para evitar que haja paginação nas páginas em memória referentes aos processos dessa aplicação. Esse comando trava todas as páginas mapeadas dentro do espaço de endereçamento do processo que o chama, incluindo páginas de código, dados e segmento de pilha, assim como bibliotecas compartilhadas, dados de kernel no espaço de usuário, memória compartilhada e arquivos mapeados em memória. Todas as páginas serão mantidas na RAM até que sejam desbloqueadas. Isso evita maiores atrasos na execução das tarefas e, consequentemente, diminui a chance de perderem seu \textit{deadline}.

Ao fim do programa, o comando \emph{munlockall} é utilizado para liberar as seções de memória anteriormente travadas.

  \subsection{Adaptação da matriz de ocupação para o algoritmo Dijkstra}

Conforme supracitado, o stage retorna uma matriz baseada no mapa escolhido onde os impedimentos são representados por 1 e as posições livres são representadas por -1. Essa é a chamada \textit{matriz de ocupação}. O pŕoximo passo é transformá-la em \textit{matriz de custos}. 

Para transformar a matriz de ocupação para a matriz custos o algoritmo verifica os vizinhos de cada quadrado (vértice) do mapa observando os seguintes parâmetros:

\begin{itemize}
  \item Se o vértice bem como seus vizinhos estão livres, o custo para ir deste vértice para qualquer dos vértice vizinhos é 1.
  \item Se o vértice está livre mas algum dos vértices vizinhos está com algum obstáculo, o custo para ir do vértice para este vértice vizinho é -1
  \item Se o próprio vértice está com algum obstáculo, o custo para ir para qualquer um dos vértices vizinhos é -1.
  \item O custo para ir de qualquer vértice para um vértice que não seja seu vizinho é -1.

\end{itemize}

Uma vez gerada a matriz de custos, a mesma é linearizada (as linhas são enfileiradas) transformando-se no formato aceito pelo processo que roda o algoritmo de Dijkstra: um \textit{vetor} de custos.

 \subsection{Cálculo das coordenadas de cada vértice}

Para representar as coordenadas x e y de cada vértice do mapa, foi criada uma struct chamada produto cartesiano:

\begin{verbatim}
typedef struct 
{
   double coordenada_x;
   double coordenada_y;
} produto_cartesiano;
\end{verbatim}

Para calcular as coordenadas de cada vértice, é calculado o ponto central do mapa (lado do mapa / 2). Esse ponto será a origem cartesiana (0,0). Calcula-se então quão longe o vértice está do centro da matriz (deslocamento positivo ou negativo), determina-se a proporção dessa distância para a distância à origem cartesiana obtendo-se as coordenadas x e y do vértice.

 \subsection{Movimentação do robô}

Uma vez determinado pelo algoritmo de Dijkstra o caminho entre o vértice origem e o destino, o algoritmo entra em um laço de repetição em que realiza três passos para cada um dos vértices do caminho. Os três passos, respectivamente são:

\begin{enumerate}

\item Determinar as coordenadas do próximo vértice do caminho;
\item Calcular as velocidades (angular e linear) para atingir as coordenadas determinadas;
\item Movimentar com o robô até que o mesmo se encotre nas coordenadas determinadas o bastante próxima (100 iterações de aproximação) da mesma;
 
\end{enumerate}
 
No momento em que chega ao último quadrado do caminho retornado pelo Dijkstra, o robô se encontra no desetino definido e o laço de repetição termina.


\section{Compilação e Execução}

A compilação pode ser feita através dos seguintes comandos:

\begin{verbatim}
gcc -Wall -o scheduler.o -c scheduler.c -lrt
g++ -o exe dijkstra.c `pkg-config --cflags playerc++` 
           fonte.cc `pkg-config --libs playerc++`
\end{verbatim}

A execução do programa deve ser feita como superusuário, como mostrado a seguir.

\begin{verbatim}
./scheduler <my_prio> <path_prog1> <deadline_prog1> ... 
                      <path_progn> <deadline_progn>
\end{verbatim}

O primeiro parâmetro de execução é a prioridade do processo pai (não dos processos que cuidaram das tarefas). Os caminhos (\textit{path\_prog}) para os programas devem ser completos.

\section{Testes}

O primeiro teste foi realizado em um mapa representado pela seguinte figura:

\begin{figure}
  \includegraphics[scale=0.5]{mapa_teste.png}
\end{figure}

O robô começava a direita de um obstáculo. Ele deveria descer até o último quadrado do mapa, virar 90 graus à sua esquerda, andar até o último quadrado do mapa, virar 90 graus à sua esquerda, subir até o último quadrado no qual alcançaria o destino.


\section{Análise de Resultados}

O robô se comportou de maneira perfeita em testes com mapas pequenos. Percorreu todo o seu percurso calcuando os próximos quadrados, definiu as velocidades angulares de maneira correta e chegou ao seu destino exatamente no centro do quadrado final.

Para mapas maiores, o robô se comportou bem, mas não de maneira perfeita: ele realizava o caminho que deveria realizar, contudo, devio a uma pequena aproximação da posição no qual o robô estava para a qual ele deveria estar em cada quadrado, esses erros foram sendo acumulados e, ao final do percurso, o robô não se localizava exatamente ao centro do quadrado.

\section{Conclusões}

Após o desenvolvimento do trabalho foi possível concluir que a grande dificuldade em aplicações de robótica, similares à qual desenvolvemos, é a precedência de alguns processos sobre outros, fato esse motivado pela dependência de dados entre os processos na qual alguns processos dependem de dados que são forncecidos e determinados por outros processos. Assim, foi necessário que, além de implementarmos os processos rodando paralelamente, implementássemos a comunicação entre eles (IPC).

Conforme citado nas seções anteriores, a verificação de obstáculos foi feita em tempo de compilação ao invés de dinamicamente. Para implementar essa verificação dinamicamente é necessario que sejam implementados 4 (quatro) passos adicionais a cada iteração do loop de repetição citado na seção 3.8:

\begin{itemize}
  \item A função para obtenção da matriz de ocupação deve ser chamada. Ainda, a matriz de ocupação deve ser convertida no vetor de custos (Seção 3.6).
  \item O algoritmo de Dijkstra deve ser chamado passando como vértice de origem o último vértice alcançado pelos movimentos do robô (seção 3.8). O vetor de custos passado deve ser o calculado no item anterior e o vértice de destino é o mesmo.
  \item Passar o novo caminho para a movimentação do robô (seção 3.8).
\end{itemize}

 

\nocite{*}
\bibliographystyle{plain}
%\bibliographystyle{apalike}
\renewcommand{\refname}{Referências} 
\bibliography{referencias}

\end{document}
